package com.hy.three400;

import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:无需开会的工作日
 * <p>
 * 给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，
 * 其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。
 * 返回员工可工作且没有安排会议的天数。
 * 注意：会议时间可能会有重叠。
 * User:Mr.Du
 * Date:2024/6/2
 * Time:22:12
 */
public class CountDays {

    public int countDays(int days, int[][] meetings) {
        // 使用merges会超时，难顶
        int[][] nums = merge(meetings);
        for(int[] num : nums){
            days -= num[1] - num[0] + 1;
        }
        return days;
    }

    /**
     * 合并区间。
     * 给定一个区间列表，其中每个区间用包含两个整数的数组表示，将这些区间合并成最少的非重叠区间。
     * <p>
     * 注意：输入的区间数组intervals已被排序，且每个区间都是合法的（即start1 <= end1 && start2 <= end2）。
     *
     * @param intervals 区间列表，每个区间用包含两个整数的数组表示。
     * @return 合并后的区间列表，每个区间用包含两个整数的数组表示。
     */
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        // 按区间的 start 升序排列
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });

        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] curr = intervals[i];
            // res 中最后一个元素的引用
            int[] last = res.getLast();
            if (curr[0] <= last[1]) {
                last[1] = Math.max(last[1], curr[1]);
            } else {
                // 处理下一个待合并区间
                res.add(curr);
            }
        }
        return res.toArray(new int[0][0]);
    }

    /**
     * 合并区间。
     * 给定一个包含多个区间的数组，每个区间用两个整数表示，分别是区间的开始和结束位置。
     * 该方法将这些区间合并成一个新的数组，新的数组中不包含重叠的区间。
     *
     * @param ranges 原始的区间数组，每个区间用长度为2的整数数组表示。
     * @return 返回合并后的区间数组，新的数组中不包含重叠的区间。
     */
    public int[][] merges(int[][] ranges) {
        // 使用BitSet来高效地表示每个位置的状态，0表示未被占用，1表示被占用。
        BitSet bitSet = new BitSet();
        // n用于记录所有区间覆盖的最远位置，确保遍历的完整性。
        int n = 0;
        // 遍历原始的区间数组，将每个区间转换为BitSet中的连续置为true的段。
        for (int[] range : ranges) {
            // 区间的结束位置转换为BitSet中的索引，由于BitSet是偶数索引表示开始，奇数索引表示结束，因此需要乘2并加1。
            int odd = range[1] * 2 + 1;
            // 将区间开始位置到结束位置的奇数索引置为true。
            bitSet.set(range[0] * 2, odd, true);
            // 更新n为所有区间覆盖的最远位置中的最大值。
            n = n >= odd ? n : odd;
        }
        // i和j用于遍历和重构区间数组。
        int i = 0, j = 0;
        // 遍历BitSet，提取出连续置为true的段，重构为区间。
        while (i < n) {
            // 获取第一个置为true的索引，即一个区间的开始位置。
            int start = bitSet.nextSetBit(i);
            // 获取第一个置为false的索引，即一个区间的结束位置。
            int end = bitSet.nextClearBit(start);
            // 重构区间，将BitSet的索引转换回原区间数组的格式。
            ranges[j++] = new int[]{start / 2, (end - 1) / 2};
            // 更新i为当前区间的结束位置，继续寻找下一个区间。
            i = end;
        }
        // 根据重构的区间数量，创建新的区间数组。
        int[][] res = new int[j][2];
        // 将重构的区间复制到新的数组中。
        for (i = 0; i < j; i++) {
            res[i] = ranges[i];
        }
        // 返回合并后的区间数组。
        return res;
    }

}
